面试题 01.05.一次编辑

1、题干

字符串有三种编辑操作:插入一个英文字符、删除一个英文字符或者替换一个英文字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。

 

示例 1:

输入: 
first = "pale"
second = "ple"
输出: True

 

示例 2:

输入: 
first = "pales"
second = "pal"
输出: False

2、解题思路

顺序遍历统计左半边相同字符总数 sl，倒序遍历统计右半边相同字符总数 sr，两字符串最大长度与 sl + sr 之差不大于 $1$ 则返回 true，否则返回 false。

两个字符串长度差值大于 $1$ 则直接返回 false，这一前置判断可有可无

3、代码

var oneEditAway = function (first, second) {
    if (Math.abs(first.length - second.length) > 1) return false;

    let sl = 0, sr = 0, m = first.length, n = second.length;
    for (let i = 0; i < Math.min(m, n) && first[i] === second[i]; i++) sl++;
    for (let i = m - 1, j = n - 1; sl - 1 < Math.min(i, j) && first[i] === second[j]; i--, j--) sr++;

    return Math.max(m, n) - sl - sr <= 1;
};

4、执行结果

• 执行用时: 64 ms
• 内存消耗: 42.7 MB